package com.cloud.lru;

import javax.print.Doc;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author tangyuan2meicloud.com
 * @DATE 2021/7/8 9:28
 * @Desc
 * @Remarks
 */
public class LRUArth<K, V> {

    class Node<K, V> {
        K key;
        V value;
        Node<K, V> next;
        Node<K, V> prev;

        public Node() {
        }

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.next = null;
            this.prev = null;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }

    class DoubleLinkedList<K, V> {
        Node<K, V> head;
        Node<K, V> last;

        public DoubleLinkedList() {
            head = new Node();
            last = new Node();
            head.next = last;
            last.prev = head;
        }

        public void removeNode(Node temp) {
            temp.next.prev = temp.prev;
            temp.prev.next = temp.next;
            temp.next = null; //help GC
            temp.prev = null; //help GC
        }

        public void addFirst(Node temp) {
            temp.next = head.next;
            head.next.prev = temp;
            head.next = temp;
            temp.prev = head;
        }

        public Node<K, V> getLastNode() {
            if (last.prev != head) {
                return last.prev;
            }
            return null;
        }
    }

    Map<K, Node<K, V>> map;
    DoubleLinkedList<K, V> doubleLinkedList;

    int maxSize;

    public void add(K key, V value) {
        if (map.containsKey(key)) {
            Node<K, V> kvNode = map.get(key);
            doubleLinkedList.removeNode(kvNode);
            kvNode.setValue(value);
            map.put(key, kvNode);
            doubleLinkedList.addFirst(kvNode);
        } else {
            Node<K, V> kvNode = new Node<>(key, value);
            if (map.size() < maxSize) {
                map.put(key, kvNode);
                doubleLinkedList.addFirst(kvNode);
            } else {
                Node<K, V> lastNode = doubleLinkedList.getLastNode();
                if (lastNode != null) {
                    K k = lastNode.getKey();
                    map.remove(k);
                    doubleLinkedList.removeNode(lastNode);
                    doubleLinkedList.addFirst(kvNode);
                    map.put(key, kvNode);
                }
            }
        }
    }

    public LRUArth(int maxSize) {
        this.maxSize = maxSize;
        map = new HashMap<>();
        doubleLinkedList = new DoubleLinkedList<>();
    }

    public static void main(String[] args) {
        LRUArth<Integer, Integer> lruArth = new LRUArth<>(3);
        lruArth.add(1, 1);
        lruArth.add(2, 2);
        lruArth.add(3, 3);
        System.out.println(lruArth.map.keySet());
        lruArth.add(4, 4);
        System.out.println(lruArth.map.keySet());
        lruArth.add(2, 2);
        System.out.println(lruArth.map.keySet());
        lruArth.add(5, 5);
        System.out.println(lruArth.map.keySet());
        lruArth.add(6, 6);
        System.out.println(lruArth.map.keySet());
    }

}
